package com.hr.leetcode.字符串;

import java.util.Arrays;

/**
 * 字符串模式匹配之KMP算法
 *
 * @author zhz
 * @date 2020/09/16
 **/
public class 字符串模式匹配之KMP算法 {
    public static void main(String[] args) {
        //主串
        String destStr = "BABABACABABCABAABD";
        //模式串（子串）
        String subStr = "ABABCABAAB";
        //测试next数组
        int[] next = getNext(subStr);
        System.out.println(Arrays.toString(next));
        //测试KMP算法
        System.out.println(kmpSearch(destStr, subStr));
    }

    /**
     * 获取
     *
     * @param subStr 模式串（子串）
     * @return
     */
    public static int[] getNext(String subStr) {
        //1、定义一个next数组
        int[] next = new int[subStr.length()];
        //2、设置next数组的第一个元素值为-1
        next[0] = -1;
        //3、定义两个变量
        int y = 0;
        int len = -1;
        //4、定义一个循环，用于计算next数组
        while (y < subStr.length() - 1) {
            //5、处理len和y指向模式串（子串）中的字符串相等的情况
            if (len == -1 || subStr.charAt(len) == subStr.charAt(y)) {
                //如果len和y指向的字符串相等，那么就执行next[y]=next[len]
                if (subStr.charAt(++len) == subStr.charAt(++y)) {
                    next[y] = next[len];
                } else {
                    next[y] = len;
                }
            } else {//6、处理len和y指向模式串中的字符不相等的情况
                len = next[len];
            }
        }
        //7、返回计算出来的next的数组
        return next;

    }

    /**
     * 实现KMP算法
     *
     * @param destStr 主串
     * @param subStr  子串
     * @return 返回模式串的第一个字符在主串中的索引位置，如果主串中不存在该模式串，则返回-1
     */
    public static int kmpSearch(String destStr, String subStr) {
        //0、计算next数组
        int[] next = getNext(subStr);
        //1、定义一个指针，用于指向主串中的第一个字符
        int x = 0;
        //2、定义一个指针，用于指向模式串（子串）中的第一个字符
        int y = 0;
        //3‘定义一个循环，用于实现字符串的匹配操作
        while (x < destStr.length() && y < subStr.length()) {
            //4、如果相等，则继续逐个比较后续字符
            if (y == -1 || destStr.charAt(x) == subStr.charAt(y)) {
                x++;
                y++;
            } else {//5、如果不相等，则从主串的狭隘一个字符起，重新与模式串的第一个字符串进行比较
                //x=x-y+1;
                y = next[y];
            }
        }
        //6、如果模式串遍历完毕，则证明匹配成功，否则就证明匹配失败
        if (y == subStr.length()) {
            return x - y;
        } else {
            return -1;
        }
    }
}
